package edu.rit.checkers;

import java.util.Comparator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

import edu.rit.pj.Comm;

/**
 * @author Ian Tewskbury (ict8574@rit.edu)
 */
public class CheckersSeq {
	/**
	 * The usage message for running this program
	 */
	private static final String USAGE =
		"usage: CheckersSeq " +
		"<startDepth> <increaseDepth> <maxTime> <maxTimePerDepth>\n" +
		"<startDepth> the start depth of the tree\n" +
		"<increaseDepth> the amount to increase the depth " +
			"of the tree by if time allows\n" +
		"<maxTime> the max time to run the search\n" +
		"<maxTimePerDepth> the max time to spend searching " +
			"each depth increase\n";

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		//PJ init
		Comm.init(args);
		
		int[] parsedArgs = CheckersSeq.parseArgs(args);
		
		if(parsedArgs != null) {
			CheckersSeq.runSeqTest(parsedArgs[0], parsedArgs[1], parsedArgs[2],
				parsedArgs[3], true);
		}
	}
	
	/**
	 * 
	 * @param args
	 * @return
	 */
	private static int[] parseArgs(String[] args){
		int[] parsedArgs = null;
		
		if(args.length == 4) {
			parsedArgs = new int[4];
			try {
				parsedArgs[0] = Integer.parseInt(args[0]);
				parsedArgs[1] = Integer.parseInt(args[1]);
				parsedArgs[2] = Integer.parseInt(args[2]);
				parsedArgs[3] = Integer.parseInt(args[3]);
			} catch(NumberFormatException e) {
				parsedArgs = null;
				System.out.println(USAGE);
			}
		} else {
			System.out.println(USAGE);
		}
		
		return parsedArgs;
	}
	
	/**
	 * 
	 * @param args
	 * @return
	 * @throws Exception
	 */
	public static long runSeqTest(int startDepth, int depthIncrease,
			int timeLimit, int timeLimitForDepth, boolean printInfo)
		throws Exception {
		
		long tStart, tABStart;
		
		//get start time
		tStart = System.currentTimeMillis();
		
		//create logger
		Logger log = new Logger(System.out);
		log.loggerOn(printInfo);
		
		//build the tree
		log.println("SEARCH TREE");
		ConfigTree tree = null;
		tree = CheckersSeq.buildTree(startDepth, depthIncrease, timeLimit,
			timeLimitForDepth);
		
		//print tree info and search time
		log.println(tree);
		log.println("Search Time: " +
			(System.currentTimeMillis() - tStart));
		
		//do a final alpha beta and print its running time
		log.println("\nFINAL ALPHA-BETA");
		tABStart = System.currentTimeMillis();
		tree.alphaBeta();
		log.println(tree);
		log.println("Final Alpha-Beta Time: " +
			(System.currentTimeMillis() - tABStart));
		
		//return total running time
		log.println("Total Time: " +
			(System.currentTimeMillis() - tStart));
		
		return tree.size();
	}
	
	/**
	 * 
	 * @param timeLimit
	 * @param timeLimitForDepth
	 * @return
	 */
	private static ConfigTree buildTree(int startDepth, int depthIncrease,
		int timeLimit, int timeLimitForDepth) {
		
		ConfigNode root = new ConfigNode();
		ConfigTree tree = new ConfigTree(startDepth, root, false);
		
		//when exploring nodes need to start with the lowest farthest left for
		//	depth first search
		SortedSet<ConfigNode> localUnexploredNodes = new TreeSet<ConfigNode>(
			new Comparator<ConfigNode>() {
				/**
				 * 
				 * @param o1
				 * @param o2
				 * @return
				 */
				public int compare(ConfigNode o1, ConfigNode o2) {
					//explore deeper nodes first
					int retVal = o2.depth - o1.depth;
					if(retVal == 0) {
						//explore furtherest left nodes first
						retVal = o1.nodeNum - o2.nodeNum;
					}
					
					return retVal;
				}
			});
		//while there is still time keep exploring
		List<ConfigNode> children;
		ConfigNode unexploredNode;
		final long tStartTotal = System.currentTimeMillis();
		while((System.currentTimeMillis() - tStartTotal) < timeLimit) {
			
			boolean atMaxDepth = false;
			long tStartDepth = System.currentTimeMillis();
			while(  tree.hasUnassignedNodes() &&
				(System.currentTimeMillis() - tStartDepth) <
					timeLimitForDepth
				&& (System.currentTimeMillis() - tStartTotal) <
					timeLimit) {
				
				//get the next unassigned node
				ConfigNode assignedNode = tree.getNextUnassignedNode();
				if(assignedNode != null) {
					//generate its children
					assignedNode.generateChildren();
					
					//TODO EXPLAIN
					if(assignedNode.children.size() > 1) {
						tree.addNode(assignedNode.children.get(0), false);
						
						children = assignedNode.children.subList(1, assignedNode.children.size());
						atMaxDepth = !tree.addNodes(children, true);
					
					} else {
						children = assignedNode.children;
						atMaxDepth = !tree.addNodes(children, true);
					}
					
					if(!atMaxDepth) {							
						//because we told the tree the children are
						//	assigned we need to explore them up to max
						//	depth or max time
						localUnexploredNodes.addAll(children);
						
						//explore local nodes
						while(!localUnexploredNodes.isEmpty() &&
							(System.currentTimeMillis() - tStartDepth) <
								timeLimitForDepth) {
							
							//get the next unexplored node
							unexploredNode = localUnexploredNodes.first();
							localUnexploredNodes.remove(unexploredNode);
							
							
							unexploredNode.generateChildren();
							children = unexploredNode.children;
							atMaxDepth = !tree.addNodes(children, true);
							
							if(!atMaxDepth) {
								localUnexploredNodes.addAll(children);
							}
						}
						
						if(!localUnexploredNodes.isEmpty()) {
							tree.addNodes(localUnexploredNodes, false);
						}
					}//END if not at max depth
					
				}//END if assigned node not null
			}//END while and max time, and depth time
			
			//only do this if we have more time, otherwise we have run out of
			//	time and will return the current tree
			if((System.currentTimeMillis() - tStartTotal) < timeLimit) {
				
				//TODO REMOVE ME
				System.out.println("BEFORE alpha beta and increase depth. added = " + tree.addedNodes());
				
				tree.alphaBeta();
				tree.increaseMaxDepth(depthIncrease);
			
				//TODO REMOVE ME
				System.out.println(" AFTER alpha beta and increase depth.");
				
			}
		}
		
		return tree;
	}

}
